#include <iostream>
#include <queue>

#define INT_MAX       1000

using namespace std;

int main(int argc, char const *argv[])
{
    int graph[10][10];
    for (size_t i = 0; i < 10; i++) 
        for (size_t j = 0; j < 10; j++)
            graph[i][j] = INT_MAX;

    graph[0][1] = 5;
    graph[1][6] = 60;
    graph[1][5] = 30;
    graph[1][2] = 20;
    graph[2][3] = 10;
    graph[2][4] = 75;
    graph[3][2] = -15;
    graph[4][9] = 100;
    graph[5][4] = 25;
    graph[5][6] = 5;
    graph[5][8] = 50;
    graph[6][7] = -50;
    graph[7][8] = -10;

    int dis[10];
    for (size_t i = 0; i < 10; i++) dis[i] = INT_MAX;
    dis[0] = 0;

    for (size_t ii = 0; ii < 2; ii++)
    {
        queue<int> q = queue<int>();
        q.push(0);
        int tag[10] = { 0 };
        tag[0] = 1;

        while (!q.empty())
        {
            int crt = q.front();
            tag[crt] = 0;
            q.pop();

            for (size_t i = 1; i < 10; i++)
            {
                if (graph[crt][i] != INT_MAX)
                {
                    if (dis[i] > dis[crt] + graph[crt][i])
                    {
                        dis[i] = dis[crt] + graph[crt][i];
                        if (!tag[i])
                        {
                            tag[i] = 1;
                            q.push(i);
                        }
                    }
                }
            }
        }

        for (size_t i = 0; i < 10; i++)
        {
            cout << i << ":" << dis[i] << "\n";
        }
        cout << endl;
    }    

    return 0;
}
